package net.lainiao.leetcode;

import net.lainiao.leetcode.base.TreeNode;

import java.util.Stack;

public class LintCode95 {
    ///验证二叉查找树
    public static void main(String[] args) {
        LintCode95 code=new LintCode95();
        TreeNode root=new TreeNode(2);
//        root.left=new TreeNode(1);
//        root.right=new TreeNode(4);
//        root.right.left=new TreeNode(3);
//        root.right.right=new TreeNode(5);
//
//        boolean isOk=code.isValidBST(root);
//        System.out.println(isOk==true);

        root=new TreeNode(10);
        root.left=new TreeNode(5);
        root.left.right=new TreeNode(6);
        root.right=new TreeNode(15);
        root.right.left=new TreeNode(14);
        root.right.right=new TreeNode(20);
        boolean isOk1=code.isValidBST(root);
        System.out.println(isOk1==false);
    }

    public  boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode preNode=null;
        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }
            else{
                root=stack.pop();
                if(preNode!=null&&preNode.val>=root.val){
                    return false;
                }
                preNode=root;
                root=root.right;
            }
        }
        return  true;
    }
}

